//
//  50.数组中重复的数字.swift
//  数据结构与算法
//
//  Created by ZERO on 2021/5/31.
//

import Foundation
/*
 题目：在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任一一个重复的数字。 例如，如果输入长度为7的数组[2,3,1,0,2,5,3]，那么对应的输出是2或者3。存在不合法的输入的话输出-1
 思路1：类似重复性问题可以用Set集合或者字典计数
 思路2：利用题目条件所有数字都是在0到n-1，
       替换法（O(n),O(1)）
       数组存放原则：numbers[i] = i
       遍历数组所有元素，交换不符合数组存放原则的元素：
           例如[2,3,1,0,2]
           遍历0位元素2：（交换0位元素2和2位元素1）->[1,3,2,0,2]
           遍历0位元素1：（交换0位元素1和1位元素3）->[3,1,2,0,2]
           遍历0位元素3：（交换0位元素3和3位元素0）->[0,1,2,3,2]
           依次遍历0、1、2、3位置元素，都符合存放原则numbers[i] = i，不做任何操作
           遍历末位元素2，此时末位元素2和2位元素2相等，出现了两次，即数字2位重复元素
 思路3：题⽬⾥写了数组⾥数字的范围保证在0 ~ n-1       之间，所以可以利⽤现有数组设置标志，当⼀个数字被访问过后，可以设置对应位上 的数 +     n，之后再遇到相同的数时，会发现对应位上的数已经⼤于等于n了，那么直接返回这个数即可。
 */
func offer_50() {
    print(Solution().duplicate3([2,3,1,0,2,5,3]))
}

fileprivate class Solution {
    func duplicate1(_ numbers: [Int]) -> Int {
        var numSet = Set<Int>()
        for num in numbers {
            if numSet.contains(num) {
                return num
            } else {
                numSet.insert(num)
            }
        }
        return -1
    }
    
    func duplicate2(_ numbers: [Int]) -> Int {
        guard !numbers.isEmpty else { return -1 }
        var numbers = numbers
        var i = 0
        while i < numbers.count {
            if numbers[i] != i {
                if numbers[i] == numbers[numbers[i]] {
                    return numbers[i]
                }
                numbers.swapAt(i, numbers[i])
                //遍历完0位元素以及交换完数字后，如果0位元素仍不符合数组存放原则：numbers[i] = i，那么还要重新遍历0位元素
                i -= 1
            }
            i += 1
        }
        return -1
    }
    
    func duplicate3(_ numbers: [Int]) -> Int {
        guard !numbers.isEmpty else { return -1 }
        var numbers = numbers
        let n = numbers.count
        for i in 0..<n {
            var index = numbers[i]
            if index >= n {
                index -= n
            }
            if numbers[index] >= n {
                return index
            }
            numbers[index] += n
        }
        return -1
    }
}
